<!DOCTYPE html><html><head>
      <title>&#x6570;&#x8BBA;&#x76F8;&#x5173;</title>
      <meta charset="utf-8">
      <meta name="viewport" content="width=device-width, initial-scale=1.0">
      
      
        <script type="text/x-mathjax-config">
          MathJax.Hub.Config({"extensions":["tex2jax.js"],"jax":["input/TeX","output/HTML-CSS"],"messageStyle":"none","tex2jax":{"processEnvironments":false,"processEscapes":true,"inlineMath":[["$","$"],["\\(","\\)"]],"displayMath":[["$$","$$"],["\\[","\\]"]]},"TeX":{"extensions":["AMSmath.js","AMSsymbols.js","noErrors.js","noUndefined.js"]},"HTML-CSS":{"availableFonts":["TeX"]}});
        </script>
        <script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js"></script>
        
      
      
      
      
      
      
      
      
      
      <style>
      /**
 * prism.js Github theme based on GitHub's theme.
 * @author Sam Clarke
 */
code[class*="language-"],
pre[class*="language-"] {
  color: #333;
  background: none;
  font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace;
  text-align: left;
  white-space: pre;
  word-spacing: normal;
  word-break: normal;
  word-wrap: normal;
  line-height: 1.4;

  -moz-tab-size: 8;
  -o-tab-size: 8;
  tab-size: 8;

  -webkit-hyphens: none;
  -moz-hyphens: none;
  -ms-hyphens: none;
  hyphens: none;
}

/* Code blocks */
pre[class*="language-"] {
  padding: .8em;
  overflow: auto;
  /* border: 1px solid #ddd; */
  border-radius: 3px;
  /* background: #fff; */
  background: #f5f5f5;
}

/* Inline code */
:not(pre) > code[class*="language-"] {
  padding: .1em;
  border-radius: .3em;
  white-space: normal;
  background: #f5f5f5;
}

.token.comment,
.token.blockquote {
  color: #969896;
}

.token.cdata {
  color: #183691;
}

.token.doctype,
.token.punctuation,
.token.variable,
.token.macro.property {
  color: #333;
}

.token.operator,
.token.important,
.token.keyword,
.token.rule,
.token.builtin {
  color: #a71d5d;
}

.token.string,
.token.url,
.token.regex,
.token.attr-value {
  color: #183691;
}

.token.property,
.token.number,
.token.boolean,
.token.entity,
.token.atrule,
.token.constant,
.token.symbol,
.token.command,
.token.code {
  color: #0086b3;
}

.token.tag,
.token.selector,
.token.prolog {
  color: #63a35c;
}

.token.function,
.token.namespace,
.token.pseudo-element,
.token.class,
.token.class-name,
.token.pseudo-class,
.token.id,
.token.url-reference .token.variable,
.token.attr-name {
  color: #795da3;
}

.token.entity {
  cursor: help;
}

.token.title,
.token.title .token.punctuation {
  font-weight: bold;
  color: #1d3e81;
}

.token.list {
  color: #ed6a43;
}

.token.inserted {
  background-color: #eaffea;
  color: #55a532;
}

.token.deleted {
  background-color: #ffecec;
  color: #bd2c00;
}

.token.bold {
  font-weight: bold;
}

.token.italic {
  font-style: italic;
}


/* JSON */
.language-json .token.property {
  color: #183691;
}

.language-markup .token.tag .token.punctuation {
  color: #333;
}

/* CSS */
code.language-css,
.language-css .token.function {
  color: #0086b3;
}

/* YAML */
.language-yaml .token.atrule {
  color: #63a35c;
}

code.language-yaml {
  color: #183691;
}

/* Ruby */
.language-ruby .token.function {
  color: #333;
}

/* Markdown */
.language-markdown .token.url {
  color: #795da3;
}

/* Makefile */
.language-makefile .token.symbol {
  color: #795da3;
}

.language-makefile .token.variable {
  color: #183691;
}

.language-makefile .token.builtin {
  color: #0086b3;
}

/* Bash */
.language-bash .token.keyword {
  color: #0086b3;
}

/* highlight */
pre[data-line] {
  position: relative;
  padding: 1em 0 1em 3em;
}
pre[data-line] .line-highlight-wrapper {
  position: absolute;
  top: 0;
  left: 0;
  background-color: transparent;
  display: block;
  width: 100%;
}

pre[data-line] .line-highlight {
  position: absolute;
  left: 0;
  right: 0;
  padding: inherit 0;
  margin-top: 1em;
  background: hsla(24, 20%, 50%,.08);
  background: linear-gradient(to right, hsla(24, 20%, 50%,.1) 70%, hsla(24, 20%, 50%,0));
  pointer-events: none;
  line-height: inherit;
  white-space: pre;
}

pre[data-line] .line-highlight:before, 
pre[data-line] .line-highlight[data-end]:after {
  content: attr(data-start);
  position: absolute;
  top: .4em;
  left: .6em;
  min-width: 1em;
  padding: 0 .5em;
  background-color: hsla(24, 20%, 50%,.4);
  color: hsl(24, 20%, 95%);
  font: bold 65%/1.5 sans-serif;
  text-align: center;
  vertical-align: .3em;
  border-radius: 999px;
  text-shadow: none;
  box-shadow: 0 1px white;
}

pre[data-line] .line-highlight[data-end]:after {
  content: attr(data-end);
  top: auto;
  bottom: .4em;
}html body{font-family:"Helvetica Neue",Helvetica,"Segoe UI",Arial,freesans,sans-serif;font-size:16px;line-height:1.6;color:#333;background-color:#fff;overflow:initial;box-sizing:border-box;word-wrap:break-word}html body>:first-child{margin-top:0}html body h1,html body h2,html body h3,html body h4,html body h5,html body h6{line-height:1.2;margin-top:1em;margin-bottom:16px;color:#000}html body h1{font-size:2.25em;font-weight:300;padding-bottom:.3em}html body h2{font-size:1.75em;font-weight:400;padding-bottom:.3em}html body h3{font-size:1.5em;font-weight:500}html body h4{font-size:1.25em;font-weight:600}html body h5{font-size:1.1em;font-weight:600}html body h6{font-size:1em;font-weight:600}html body h1,html body h2,html body h3,html body h4,html body h5{font-weight:600}html body h5{font-size:1em}html body h6{color:#5c5c5c}html body strong{color:#000}html body del{color:#5c5c5c}html body a:not([href]){color:inherit;text-decoration:none}html body a{color:#08c;text-decoration:none}html body a:hover{color:#00a3f5;text-decoration:none}html body img{max-width:100%}html body>p{margin-top:0;margin-bottom:16px;word-wrap:break-word}html body>ul,html body>ol{margin-bottom:16px}html body ul,html body ol{padding-left:2em}html body ul.no-list,html body ol.no-list{padding:0;list-style-type:none}html body ul ul,html body ul ol,html body ol ol,html body ol ul{margin-top:0;margin-bottom:0}html body li{margin-bottom:0}html body li.task-list-item{list-style:none}html body li>p{margin-top:0;margin-bottom:0}html body .task-list-item-checkbox{margin:0 .2em .25em -1.8em;vertical-align:middle}html body .task-list-item-checkbox:hover{cursor:pointer}html body blockquote{margin:16px 0;font-size:inherit;padding:0 15px;color:#5c5c5c;background-color:#f0f0f0;border-left:4px solid #d6d6d6}html body blockquote>:first-child{margin-top:0}html body blockquote>:last-child{margin-bottom:0}html body hr{height:4px;margin:32px 0;background-color:#d6d6d6;border:0 none}html body table{margin:10px 0 15px 0;border-collapse:collapse;border-spacing:0;display:block;width:100%;overflow:auto;word-break:normal;word-break:keep-all}html body table th{font-weight:bold;color:#000}html body table td,html body table th{border:1px solid #d6d6d6;padding:6px 13px}html body dl{padding:0}html body dl dt{padding:0;margin-top:16px;font-size:1em;font-style:italic;font-weight:bold}html body dl dd{padding:0 16px;margin-bottom:16px}html body code{font-family:Menlo,Monaco,Consolas,'Courier New',monospace;font-size:.85em !important;color:#000;background-color:#f0f0f0;border-radius:3px;padding:.2em 0}html body code::before,html body code::after{letter-spacing:-0.2em;content:"\00a0"}html body pre>code{padding:0;margin:0;font-size:.85em !important;word-break:normal;white-space:pre;background:transparent;border:0}html body .highlight{margin-bottom:16px}html body .highlight pre,html body pre{padding:1em;overflow:auto;font-size:.85em !important;line-height:1.45;border:#d6d6d6;border-radius:3px}html body .highlight pre{margin-bottom:0;word-break:normal}html body pre code,html body pre tt{display:inline;max-width:initial;padding:0;margin:0;overflow:initial;line-height:inherit;word-wrap:normal;background-color:transparent;border:0}html body pre code:before,html body pre tt:before,html body pre code:after,html body pre tt:after{content:normal}html body p,html body blockquote,html body ul,html body ol,html body dl,html body pre{margin-top:0;margin-bottom:16px}html body kbd{color:#000;border:1px solid #d6d6d6;border-bottom:2px solid #c7c7c7;padding:2px 4px;background-color:#f0f0f0;border-radius:3px}@media print{html body{background-color:#fff}html body h1,html body h2,html body h3,html body h4,html body h5,html body h6{color:#000;page-break-after:avoid}html body blockquote{color:#5c5c5c}html body pre{page-break-inside:avoid}html body table{display:table}html body img{display:block;max-width:100%;max-height:100%}html body pre,html body code{word-wrap:break-word;white-space:pre}}.markdown-preview{width:100%;height:100%;box-sizing:border-box}.markdown-preview .pagebreak,.markdown-preview .newpage{page-break-before:always}.markdown-preview pre.line-numbers{position:relative;padding-left:3.8em;counter-reset:linenumber}.markdown-preview pre.line-numbers>code{position:relative}.markdown-preview pre.line-numbers .line-numbers-rows{position:absolute;pointer-events:none;top:1em;font-size:100%;left:0;width:3em;letter-spacing:-1px;border-right:1px solid #999;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none}.markdown-preview pre.line-numbers .line-numbers-rows>span{pointer-events:none;display:block;counter-increment:linenumber}.markdown-preview pre.line-numbers .line-numbers-rows>span:before{content:counter(linenumber);color:#999;display:block;padding-right:.8em;text-align:right}.markdown-preview .mathjax-exps .MathJax_Display{text-align:center !important}.markdown-preview:not([for="preview"]) .code-chunk .btn-group{display:none}.markdown-preview:not([for="preview"]) .code-chunk .status{display:none}.markdown-preview:not([for="preview"]) .code-chunk .output-div{margin-bottom:16px}.scrollbar-style::-webkit-scrollbar{width:8px}.scrollbar-style::-webkit-scrollbar-track{border-radius:10px;background-color:transparent}.scrollbar-style::-webkit-scrollbar-thumb{border-radius:5px;background-color:rgba(150,150,150,0.66);border:4px solid rgba(150,150,150,0.66);background-clip:content-box}html body[for="html-export"]:not([data-presentation-mode]){position:relative;width:100%;height:100%;top:0;left:0;margin:0;padding:0;overflow:auto}html body[for="html-export"]:not([data-presentation-mode]) .markdown-preview{position:relative;top:0}@media screen and (min-width:914px){html body[for="html-export"]:not([data-presentation-mode]) .markdown-preview{padding:2em calc(50% - 457px + 2em)}}@media screen and (max-width:914px){html body[for="html-export"]:not([data-presentation-mode]) .markdown-preview{padding:2em}}@media screen and (max-width:450px){html body[for="html-export"]:not([data-presentation-mode]) .markdown-preview{font-size:14px !important;padding:1em}}@media print{html body[for="html-export"]:not([data-presentation-mode]) #sidebar-toc-btn{display:none}}html body[for="html-export"]:not([data-presentation-mode]) #sidebar-toc-btn{position:fixed;bottom:8px;left:8px;font-size:28px;cursor:pointer;color:inherit;z-index:99;width:32px;text-align:center;opacity:.4}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] #sidebar-toc-btn{opacity:1}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc{position:fixed;top:0;left:0;width:300px;height:100%;padding:32px 0 48px 0;font-size:14px;box-shadow:0 0 4px rgba(150,150,150,0.33);box-sizing:border-box;overflow:auto;background-color:inherit}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc::-webkit-scrollbar{width:8px}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc::-webkit-scrollbar-track{border-radius:10px;background-color:transparent}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc::-webkit-scrollbar-thumb{border-radius:5px;background-color:rgba(150,150,150,0.66);border:4px solid rgba(150,150,150,0.66);background-clip:content-box}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc a{text-decoration:none}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc ul{padding:0 1.6em;margin-top:.8em}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc li{margin-bottom:.8em}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc ul{list-style-type:none}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .markdown-preview{left:300px;width:calc(100% -  300px);padding:2em calc(50% - 457px -  150px);margin:0;box-sizing:border-box}@media screen and (max-width:1274px){html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .markdown-preview{padding:2em}}@media screen and (max-width:450px){html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .markdown-preview{width:100%}}html body[for="html-export"]:not([data-presentation-mode]):not([html-show-sidebar-toc]) .markdown-preview{left:50%;transform:translateX(-50%)}html body[for="html-export"]:not([data-presentation-mode]):not([html-show-sidebar-toc]) .md-sidebar-toc{display:none}
/* Please visit the URL below for more information: */
/*   https://shd101wyy.github.io/markdown-preview-enhanced/#/customize-css */

      </style>
    </head>
    <body for="html-export">
      <div class="mume markdown-preview  ">
      <h1 class="mume-header" id="%E6%95%B0%E8%AE%BA%E7%9B%B8%E5%85%B3">&#x6570;&#x8BBA;&#x76F8;&#x5173;</h1>

<p><span id="toc"></span></p>
<ul>
<li><a href="#%E6%95%B0%E8%AE%BA%E7%9B%B8%E5%85%B3">&#x6570;&#x8BBA;&#x76F8;&#x5173;</a>
<ul>
<li><a href="#%E7%9B%B8%E5%85%B3%E6%A6%82%E5%BF%B5toc">&#x76F8;&#x5173;&#x6982;&#x5FF5;</a></li>
<li><a href="#%E5%9F%BA%E7%A1%80%E5%AE%9A%E7%90%86toc">&#x57FA;&#x7840;&#x5B9A;&#x7406;</a></li>
<li><a href="#%E8%B4%A8%E6%95%B0%E6%B5%8B%E8%AF%95toc">&#x8D28;&#x6570;&#x6D4B;&#x8BD5;</a>
<ul>
<li><a href="#miller-rabin%E9%9A%8F%E6%9C%BA%E8%B4%A8%E6%95%B0%E6%B5%8B%E8%AF%95%E7%AE%97%E6%B3%95toc">Miller-Rabin&#x968F;&#x673A;&#x8D28;&#x6570;&#x6D4B;&#x8BD5;&#x7B97;&#x6CD5;</a>
<ul>
<li><a href="#%E5%8E%9F%E7%90%86toc">&#x539F;&#x7406;</a></li>
<li><a href="#%E6%AD%A5%E9%AA%A4toc">&#x6B65;&#x9AA4;</a></li>
</ul>
</li>
</ul>
</li>
<li><a href="#%E5%8F%82%E8%80%83%E8%B5%84%E6%96%99toc">&#x53C2;&#x8003;&#x8D44;&#x6599;</a></li>
</ul>
</li>
</ul>
<h2 class="mume-header" id="%E7%9B%B8%E5%85%B3%E6%A6%82%E5%BF%B5toc"><a href="#toc">&#x76F8;&#x5173;&#x6982;&#x5FF5;</a></h2>

<p>&#x8BB0;&#x6709;&#x7FA4;<span class="mathjax-exps">$(S, \oplus)$</span>, &#x4E3A;&#x4E86;&#x65B9;&#x4FBF;&#x7B80;&#x8BB0;&#x4E3A;<span class="mathjax-exps">$S$</span>;</p>
<ul>
<li>&#x7FA4;&#x7684;&#x5B9A;&#x4E49;&#x89C1;<a href="https://www.cnblogs.com/mengsuenyan/p/13156265.html">&#x692D;&#x5706;&#x66F2;&#x7EBF;&#x52A0;&#x5BC6;&#x6570;&#x5B66;&#x57FA;&#x7840;</a>;</li>
<li>&#x7FA4;&#x7684;&#x9636;<span class="mathjax-exps">$\#S$</span>: &#x7FA4;&#x4E2D;&#x5143;&#x7D20;&#x7684;&#x4E2A;&#x6570;;</li>
<li><span class="mathjax-exps">$a\in S$</span>, &#x8BB0;<span class="mathjax-exps">$a$</span>&#x751F;&#x6210;&#x7684;&#x5B50;&#x7FA4;&#x4E3A;<span class="mathjax-exps">$\langle a \rangle$</span>, &#x751F;&#x6210;&#x8FC7;&#x7A0B;&#x4E3A;: <span class="mathjax-exps">$\{a^{(k)}=\oplus_{i=1}^{k}a, a^{(k)}\in S, k=1\cdots \}$</span>;</li>
<li><span class="mathjax-exps">$a\in S$</span>, &#x8BB0;<span class="mathjax-exps">$a$</span>&#x7684;&#x9636;<span class="mathjax-exps">$ord_{n}(a)$</span>&#x5B9A;&#x4E49;&#x4E3A;&#x6EE1;&#x8DB3;<span class="mathjax-exps">$a^n=e$</span>&#x7684;&#x6700;&#x5C0F;&#x6B63;&#x6574;&#x6570;<span class="mathjax-exps">$n$</span>, &#x5176;&#x4E2D;<span class="mathjax-exps">$e$</span>&#x8868;&#x793A;&#x8BE5;&#x7FA4;&#x7684;&#x5355;&#x4F4D;&#x5143;&#x7D20;;</li>
<li>&#x7FA4;&#x7684;&#x539F;&#x6839;(&#x751F;&#x6210;&#x5143;): &#x82E5;<span class="mathjax-exps">$\langle a \rangle = S, a\in S$</span>, &#x90A3;&#x4E48;<span class="mathjax-exps">$a$</span>&#x79F0;&#x4E3A;<span class="mathjax-exps">$a$</span>&#x7684;&#x539F;&#x6839;; &#x5BF9;&#x4E8E;&#x81EA;&#x7136;&#x6570;&#x7684;&#x6A21;<span class="mathjax-exps">$n$</span>&#x52A0;&#x6CD5;&#x7FA4;<span class="mathjax-exps">$Z_n^+$</span>, &#x82E5;<span class="mathjax-exps">$n$</span>&#x662F;&#x8D28;&#x6570;, &#x90A3;&#x4E48;&#x8BE5;&#x7FA4;&#x4E2D;&#x7684;&#x6BCF;&#x4E2A;&#x5143;&#x7D20;&#x90FD;&#x662F;&#x8BE5;&#x7FA4;&#x7684;&#x751F;&#x6210;&#x6839;; &#x4E58;&#x6CD5;&#x7FA4;<span class="mathjax-exps">$Z_n^*$</span>&#x5219;&#x4E0D;&#x4E00;&#x5B9A;;</li>
<li>&#x5FAA;&#x73AF;&#x7FA4;: &#x82E5;<span class="mathjax-exps">$S$</span>&#x4E2D;&#x5305;&#x542B;&#x4E00;&#x4E2A;&#x539F;&#x6839;, &#x90A3;&#x4E48;&#x8BE5;&#x7FA4;&#x79F0;&#x4E3A;&#x5FAA;&#x73AF;&#x7FA4;;</li>
</ul>
<h2 class="mume-header" id="%E5%9F%BA%E7%A1%80%E5%AE%9A%E7%90%86toc"><a href="#toc">&#x57FA;&#x7840;&#x5B9A;&#x7406;</a></h2>

<ul>
<li>&#x8BB0;<span class="mathjax-exps">$\pi(x)$</span>&#x4E3A;&#x4E0D;&#x5927;&#x4E8E;<span class="mathjax-exps">$x$</span>&#x7684;&#x7D20;&#x6570;&#x4E2A;&#x6570;, &#x90A3;&#x4E48;&#x6709;<span class="mathjax-exps">$\lim_{x\rightarrow \infty}\frac{\pi(x)}{x/\log(x)} = 1$</span>;</li>
<li>&#x76F8;&#x90BB;&#x4E24;&#x4E2A;&#x7D20;&#x6570;&#x7684;&#x5DEE;&#x662F;2&#x7684;&#x7D20;&#x6570;&#x5BF9;&#x53EF;&#x80FD;&#x6709;&#x65E0;&#x9650;&#x591A;&#x4E2A;;</li>
<li><span class="mathjax-exps">$a\in\{2k+1, K\in N^+\} \Rightarrow 8|(a^2-1)$</span></li>
<li>&#x8BB0;<span class="mathjax-exps">$a,b\in N^{+}\Rightarrow ab=gcd(a,b)\cdot lcm(a,b)$</span>;</li>
<li><span class="mathjax-exps">$a,b,c\in N^+, gcd(a,b)=1, gcd(a,c)&gt;1 \Rightarrow gcd(c,b)=1$</span>;</li>
<li><span class="mathjax-exps">$a, b, c\in N^+, gcd(a,b)=1 \Rightarrow gcd(a,bc)=gcd(a,c)$</span>;</li>
<li><span class="mathjax-exps">$a, b_1, b_2, \cdots, b_n\in N^+, gcd(a,b_1)=gcd(a,b_2)=\cdots=gcd(a,b_n)=1 \Rightarrow gcd(a, b_1 b_2\cdots b_n)=1$</span>;</li>
<li><span class="mathjax-exps">$a, b, n\in N^+ \Rightarrow gcd(a^n,b^n)=gcd(a,b)^n$</span>;</li>
<li><span class="mathjax-exps">$a, b, n\in N^+ \Rightarrow gcd(na,nb)=n\cdot gcd(a,b)$</span>;</li>
<li><span class="mathjax-exps">$a,b,c,d\in Z, n\in N^+,  a\equiv b\mod n, c\equiv d\mod n\Rightarrow a\pm c\equiv b\pm d \mod n$</span>;</li>
<li><span class="mathjax-exps">$a,b\in Z, n\in N^+, a\equiv b\mod n \Rightarrow n|(a-b)$</span></li>
<li><span class="mathjax-exps">$a,b,c,d\in Z, n\in N^+,  a\equiv b\mod n, c\equiv d\mod n\Rightarrow ac\equiv bd \mod n$</span>;</li>
<li><span class="mathjax-exps">$a,b\in Z, m,n\in N^+ a\equiv b\mod n \Rightarrow a^m=b^m \mod n$</span>;</li>
<li><span class="mathjax-exps">$a,b,x\in Z, n\in N^+, ax\equiv b\mod n \Rightarrow ax-b\equiv 0\mod n$</span>;</li>
<li><span class="mathjax-exps">$a,b\in Z, c,n\in N^+, ac\equiv b\mod n \Rightarrow \forall x=c\mod m, \exists\ ax-b\equiv 0\mod n$</span>;</li>
<li><span class="mathjax-exps">$a,b\in Z, n\in N^+, \not\exists\ k\in Z\to k\cdot gcd(a,n) = b \Rightarrow ax+b\equiv 0\mod n, x\in \varnothing$</span>;</li>
<li><span class="mathjax-exps">$a,b\in Z, n\in N^+, \exists\ k\in Z\to k\cdot gcd(a,n) = b \Rightarrow ax+b\equiv 0\mod n, x\not\in \varnothing$</span>;</li>
<li><span class="mathjax-exps">$a,b\in Z, n\in N^+, gcd(a,n)=d=ax&apos;+ny&apos;, k=b/d, k\in Z ax\equiv b\mod n \Rightarrow x_i = (x&apos;(b/d)\mod n) + i(n/d), i\in\{0,1,2,\cdots,d-1\}$</span>;</li>
<li><span class="mathjax-exps">$ad\equiv bd\mod nd \Rightarrow a\equiv b\mod n$</span>;</li>
<li><span class="mathjax-exps">$ad\equiv bd\mod n, gcd(d,n)=1 \Rightarrow a\equiv b\mod n$</span>;</li>
<li><span class="mathjax-exps">$\begin{aligned}&amp; \exists\{p_1,p_2,\cdots, p_k\}, \forall i,j,i\ne j\to gcd(p_i,p_j)=1, \\&amp; x\equiv b_1\mod m_1, x\equiv b_2\mod m_2,\cdots,x\equiv b_k\mod m_k \Rightarrow\\&amp; x\equiv b_1 M_1^{&apos;}M_1 + b_2 M_2^{&apos;} M_2 +\cdots b_k M_k^{&apos;} M_k\mod M\\&amp; M=m_1 m_2\cdots m_k=m_1 M_1=m_2 M_2\cdots = m_k M_k\\&amp; M_i^{&apos;}M_i\equiv 1\mod m_i, i\in \{0,1,2,\cdots,k\}\end{aligned}$</span>;</li>
<li>&#x8BB0;&#x6709;&#x6B27;&#x62C9;&#x51FD;&#x6570;<span class="mathjax-exps">$\psi(m)$</span>(&#x4E0D;&#x5927;&#x4E8E;<span class="mathjax-exps">$m$</span>&#x548C;<span class="mathjax-exps">$m$</span>&#x4E92;&#x7D20;&#x7684;&#x6B63;&#x6574;&#x6570;&#x4E2A;&#x6570;), &#x5219;&#x6709;<span class="mathjax-exps">$\psi(p^n)=p^{n-1}(p-1), n\in N^+, \{gcd(m,p)=1, \forall m\in N^+, m&lt;p\}$</span>;</li>
<li><span class="mathjax-exps">$a^{\psi(m)}\equiv 1\mod m, m\in N^+, m&gt;1, gcd(a,m)=1$</span>;</li>
<li></li>
</ul>
<h2 class="mume-header" id="%E8%B4%A8%E6%95%B0%E6%B5%8B%E8%AF%95toc"><a href="#toc">&#x8D28;&#x6570;&#x6D4B;&#x8BD5;</a></h2>

<h3 class="mume-header" id="miller-rabin%E9%9A%8F%E6%9C%BA%E8%B4%A8%E6%95%B0%E6%B5%8B%E8%AF%95%E7%AE%97%E6%B3%95toc"><a href="#toc">Miller-Rabin&#x968F;&#x673A;&#x8D28;&#x6570;&#x6D4B;&#x8BD5;&#x7B97;&#x6CD5;</a></h3>

<h4 class="mume-header" id="%E5%8E%9F%E7%90%86toc"><a href="#toc">&#x539F;&#x7406;</a></h4>

<ul>
<li>&#x8BB0;&#x6709;&#x6A21;<span class="mathjax-exps">$n$</span>&#x4E58;&#x6CD5;&#x7FA4;<span class="mathjax-exps">$Z_n^*$</span>;</li>
<li>&#x8D39;&#x9A6C;&#x5B9A;&#x7406;: &#x5982;&#x679C;<span class="mathjax-exps">$p$</span>&#x662F;&#x8D28;&#x6570;, &#x5219;&#x5BF9;&#x4E8E;<span class="mathjax-exps">$a\in Z_p^*$</span>&#x6709;<span class="mathjax-exps">$a^{p-1}\equiv 1 (\mod p)$</span>&#x6210;&#x7ACB;;</li>
<li>&#x63A8;&#x8BBA;: &#x82E5;<span class="mathjax-exps">$p$</span>&#x662F;&#x8D28;&#x6570;, &#x5219;&#x5BF9;&#x4E8E;&#x4EFB;&#x610F;&#x6574;&#x6570;<span class="mathjax-exps">$x\in [0,p)$</span>, &#x6709;<span class="mathjax-exps">$x^2 \equiv 1(\mod p)$</span>&#x7684;&#x89E3;&#x4E3A;<span class="mathjax-exps">$x=1$</span>&#x6216;<span class="mathjax-exps">$x=p-1$</span>;</li>
<li><span class="mathjax-exps">$a*b \mod n = ((a\mod n)*(b \mod n)) \mod n$</span>;</li>
</ul>
<h4 class="mume-header" id="%E6%AD%A5%E9%AA%A4toc"><a href="#toc">&#x6B65;&#x9AA4;</a></h4>

<p>&#x8BB0;&#x6709;&#x4E00;&#x4E2A;&#x5F85;&#x6D4B;&#x8BD5;&#x5947;&#x81EA;&#x7136;&#x6570;<code>a</code>, &#x53CA;&#x6D4B;&#x8BD5;&#x603B;&#x8F6E;&#x6570;<code>s</code>. Miller-Rabin&#x7B97;&#x6CD5;&#x6709;&#x5982;&#x4E0B;&#x5B9A;&#x7406;:</p>
<ul>
<li>&#x5982;&#x679C;n&#x662F;&#x4E00;&#x4E2A;&#x5947;&#x5408;&#x6570;, &#x90A3;&#x4E48;&#x6D4B;&#x8BD5;n&#x4E3A;&#x5408;&#x6570;&#x7684;&#x8BC1;&#x636E;&#x7684;&#x6570;&#x636E;&#x81F3;&#x5C11;&#x4E3A;<span class="mathjax-exps">$(n-1)/2$</span>;</li>
<li>&#x5BF9;&#x4E8E;&#x4EFB;&#x610F;<span class="mathjax-exps">$a \gt 2$</span>&#x7684;&#x5947;&#x6570;&#x548C;&#x6B63;&#x6574;&#x6570;<code>s</code>, Miller-Rabin&#x51FA;&#x9519;&#x7684;&#x6982;&#x7387;&#x81F3;&#x591A;&#x4E3A;<span class="mathjax-exps">$2^{-s}$</span>;</li>
</ul>
<p></p><div class="mathjax-exps">$$\begin{aligned} &amp; //\ &#x6D4B;&#x8BD5;&#x4E00;&#x4E2A;&#x6570;&#x662F;&#x5426;&#x662F;&#x5408;&#x6570; \\ &amp; WITNESS(a, n) \\ &amp; \quad n-1 = 2^{t}*u,\ a \% 2=1\\ &amp; \quad x_0 = a^{u} \% n \\ &amp; \quad for\ i\ in\ 1..=t \\ &amp; \quad \quad x_i = x_{i-1}^{2} \% n \\ &amp; \quad \quad if\ x_i = 1\ \And\And\ x_{i-1} \ne 1\ \And\And\ x_{i-1}\ne n-1\\ &amp; \quad \quad \quad return\ true\\ &amp; \quad \quad end \\ &amp; \quad end\\ &amp; \quad \\ &amp; \quad if\ x_t \ne 1\\ &amp; \quad \quad return\ true\\ &amp; \quad end\\ &amp; \quad return\ false\\ &amp; end &amp; \quad \\ &amp; \quad \\ &amp; // &#x6D4B;&#x8BD5;&#x5947;&#x81EA;&#x7136;&#x6570;n&#x662F;&#x8D28;&#x6570;&#x8FD8;&#x662F;&#x5408;&#x6570; \\ &amp; MILLER-RABIN(n,s)\\ &amp; \quad for\ j\ in\ 0..s\\ &amp; \quad \quad a=RANDOM(1,n)\\ &amp; \quad \quad if\ WITNESS(a,n) \\ &amp; \quad \quad \quad return\ COMPOSITE \\ &amp; \quad \quad end\\ &amp; \quad return\ PRIME\\ &amp; end \\ \end{aligned}$$</div><p></p>
<h2 class="mume-header" id="%E5%8F%82%E8%80%83%E8%B5%84%E6%96%99toc"><a href="#toc">&#x53C2;&#x8003;&#x8D44;&#x6599;</a></h2>

<ul>
<li><a href="https://book.douban.com/subject/20432061/">&#x7B97;&#x6CD5;&#x5BFC;&#x8BBA;</a>;</li>
</ul>

      </div>
      
      
    
    
    
    
    
    
    
    
  
    </body></html>